
/* 汉诺塔, 非递归实现 */

#include<iostream>
#include<stack>
#include<list>
#include<cstdlib>
#include<algorithm>
#include<thread>
using namespace std;

constexpr int N = 6;

struct THanoi
{
	int n;
	char src;
	char mid;
	char dest;

	THanoi(int i, char s, char m, char d)
		: n(i)
		, src(s)
		, mid(m)
		, dest(d)
	{
	}
};

list<int> listHanoi[3];
void Step(const THanoi& t)
{
	char src = t.src;
	char dest = t.dest;

	int idxSrc = src - 'A';
	int idxDest = dest - 'A';

	int v = listHanoi[idxSrc].back();
	listHanoi[idxSrc].pop_back();
	listHanoi[idxDest].push_back(v);

	system("clear");
	for (int i = 0; i < 3; i++)
	{
		cout << (char)('A' + i) << ": ";
		for_each(listHanoi[i].begin(), listHanoi[i].end(), [](int e) -> void {cout << e << " "; });
		cout << "\n";
	}
	this_thread::sleep_for(500ms);
}


void Hanoi(int n, char src, char mid, char dest)
{
	stack<THanoi> stHanoi;
	stHanoi.push(THanoi(n, src, mid, dest));

	while (!stHanoi.empty())
	{
		THanoi t = stHanoi.top();	//取当前任务
		stHanoi.pop();			//删除当前任务

		if (t.n == 1)
		{
			Step(t);
		}
		else				//分解当前任务
		{
			/* 注意，分解任务是第1步、第2步、第3步，然而push到栈中是按第3步、第2步、第1步的顺序来的 */
			stHanoi.push(THanoi(t.n - 1, t.mid, t.src, t.dest));
			stHanoi.push(THanoi(1, t.src, t.mid, t.dest));
			stHanoi.push(THanoi(t.n - 1, t.src, t.dest, t.mid));
		}
	}

}

int main(void)
{
	for (int i = N; i > 0; i--)
	{
		listHanoi[0].push_back(i);
	}

	Hanoi(N, 'A', 'B', 'C');
}

